/* 常用的Hash函数(BKDR,FNV,DJB,ELF,bobJenkins,Murmur,crc32)
 * cel hash function implemented source file
 * @author chenxin <chenxin619315@gmail.com>
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h> //uint32_t
#include <string.h>

/* get 32 bits */
#undef get32bits
#if ( defined(__GNUC__) || defined(__i386__) || defined(__WATCOMC__) \
		|| defined(_MSC_VER) || defined(__BORLANDC__) || defined(__TURBOC__) )
#define get32bits(d) (*((const uint32_t *) (d)))
#endif

#if ! defined(get32bits)
//type of d should be char *
#define get32bits(d) ( (uint32_t)(d)[0] 	\
		+ ((uint32_t)(d)[1] << 8)			\
		+ ((uint32_t)(d)[2] << 16)			\
		+ ((uint32_t)(d)[3] << 24) )
#endif

/* get 16 bits */
#undef get16bits
#if ( defined(__GNUC__) || defined(__i386__) || defined(__WATCOMC__) \
		|| defined(_MSC_VER) || defined(__BORLANDC__) || defined(__TURBOC__) )
#define get16bits(d) (*((const uint16_t *) (d)))
#endif

#if ! defined(get16bits)
//type of d should be char *
#define get16bits(d) ( (uint16_t)(d)[0]	+ ((uint16_t)(d)[1] << 8) )
#endif

//simple BKDR hash algorithm
uint32_t cel_bkdr_hash(const char * str)
{
	register uint32_t h = 0;
	uint32_t seed = 131;	//31 131 1313 13131

	while(*str != '\0') 
	{
		h = h * seed + (*str++); 
	}

	return (h & 0x7FFFFFFF);
}

/*
 * FNV hash algorithm. wildly use in Unix system.
 */
uint32_t cel_fnv_hash(const char *str)
{
	register uint32_t h = 2166136261UL;
	uint32_t prime = 16777619;

	while (*str != '\0') 
	{
		h *= prime;
		h ^= *str++;
	}

	return (h & 0x7FFFFFFF);
}

/*
 * FNV-1a hash algorithm. wildly use in Unix system.
 * the only difference between FNV-1 is the order of xor and multipy.
 */
uint32_t cel_fnv1a_hash(const char *str)
{
	register uint32_t h = 2166136261UL;
	uint32_t prime = 16777619;

	while(*str != '\0') 
	{
		h ^= (*str++);
		h *= prime;
	}

	return (h & 0x7FFFFFFF);
}

/*
 * AP hash algorithm. design by Arash Partow.
 */
uint32_t cel_ap_hash(const char *str)
{
	register uint32_t i = 0, h = 0;

	while(*str != '\0') 
	{
		if((i++ & 1) == 0) 
		{
			h ^= ((h << 7) ^ (*str++) ^ (h << 3));
		} 
		else 
		{
			h ^= (~((h << 11) ^ (*str++) ^ (h << 5)));
		}
	}

	return (h & 0x7FFFFFFF);
}

/*
 * DJP hash algorithm. invented by doctor Daniel J. Bernstein.
 */
uint32_t cel_djp_hash(const char *str)
{
	register uint32_t h = 5381;

	while(*str != '\0') 
	{
		h += (h << 5) + (*str++);
	}

	return (h & 0x7FFFFFFF);
}

/*
 * DJP hash algorithm 2. invented by doctor Daniel J. Bernstein.
 */
uint32_t cel_djp2_hash(const char *str)
{
	register uint32_t h = 5381;

	while(*str != '\0') 
	{
		h = h * 33 ^ (*str++);
	}

	return (h & 0x7FFFFFFF);
}

/*
 * JS hash algorithm. invented by Justin Sobel.
 */
uint32_t cel_js_hash(const char *str)
{
	register uint32_t h = 0;

	while(*str != '\0') 
	{
		h ^= ((h << 5) + (*str++) + (h << 2));
	}

	return (h & 0x7FFFFFFF);
}

/*
 * SDMS hash algorithm. came from open source simple database engin SDMS.
 */
uint32_t cel_sdms_hash(const char * str)
{
	register uint32_t h = 0;

	while (*str != '\0') 
	{
		h = 65599 * h + (*str++);
	}

	return (h & 0x7FFFFFFF);
}

/*
 * RS hash algoritm. came from book [Algorithm in c] Written by Robert Sedgwicks.
 */
uint32_t cel_rs_hash(const char *str)
{
	register uint32_t h = 0;
	register uint32_t magic = 63689;

	while(*str != '\0') 
	{
		h = h * magic + (*str++);
		magic *= 378551;
	}

	return (h & 0x7FFFFFFF);
}

/*
 * DEK hash algorithm. came from [Art of Computer programing Volumes 3]
 * written by Donald E.knuth.
 */
uint32_t cel_dek_hash(const char *str)
{
	register uint32_t h = 0;

	while (*str != '\0') 
	{
		h = ((h << 5) ^ (h >> 27) ^ (*str++));
	}

	return (h & 0x7FFFFFFF);
}

/*
 * ELF hash algorithm. executable and linking Format.
 */
uint32_t cel_elf_hash(const char * str)
{
	register uint32_t h = 0;
	register uint32_t x = 0;

	while (*str != '\0') 
	{
		h = (h << 24) + (*str++);
		if ((x = h & 0xF0000000L) != 0) 
		{
			h ^= (h >> 24);
			h &= ~x;
		}
	}

	return (h & 0x7FFFFFFF);
}

#define cel_bj_mix( a, b, c ) \
{\
	a -= b; a -= c; a ^= (c>>13);	\
	b -= c; b -= a; b ^= (a<<8);	\
	c -= a; c -= b; c ^= (b>>13);	\
	a -= b; a -= c; a ^= (c>>12);	\
	b -= c; b -= a; b ^= (a<<16);	\
	c -= a; c -= b; c ^= (b>>5);	\
	a -= b; a -= c; a ^= (c>>3);	\
	b -= c; b -= a; b ^= (a<<10);	\
	c -= a; c -= b; c ^= (b>>15);	\
}

/*
 * Bob Jenkins hash algorithm.
 * @length, the length of the key in bytes
 * @initval, the previous hash, or an arbitrary value
 */
uint32_t cel_bobJenkins_hash32(const void * str, unsigned int length, uint32_t initval)
{
	register uint32_t a,b,c;
	register uint32_t len;	/*how many bytes still need to mixing*/
	unsigned char * k = (unsigned char *) str;

	//Set up internal state.
	len = length;
	a = b = 0x9e3779b9;		/*Golden ratio: an arbitrary value.*/
	c = initval;		/*variable initialization of internal state*/

	//handle most of the bytes of the str
	while ( len >= 12 )
	{
		a += get32bits(k);
		b += get32bits(k + 4);
		c += get32bits(k + 8);
		cel_bj_mix(a, b, c);
		k += 12; len -= 12;
	}

	//handle the last 11 bytes
	c += length;
	switch ( len ) 
	{
		/* all the case statements fall through */
		case 11: c+=((uint32_t)k[10]<<24);
		case 10: c+=((uint32_t)k[9]<<16);
		case 9 : c+=((uint32_t)k[8]<<8);
				 // the first byte of c is reserved for the length 
		case 8 : b+=((uint32_t)k[7]<<24);
		case 7 : b+=((uint32_t)k[6]<<16);
		case 6 : b+=((uint32_t)k[5]<<8);
		case 5 : b+=k[4];
		case 4 : a+=((uint32_t)k[3]<<24);
		case 3 : a+=((uint32_t)k[2]<<16);
		case 2 : a+=((uint32_t)k[1]<<8);
		case 1 : a+=k[0];
				 /* case 0: nothing left to add */
	}
	cel_bj_mix(a,b,c);

	return c;
}

uint32_t cel_bobJenkins32_hash(const char * str)
{
	return cel_bobJenkins_hash32(str, strlen(str), 0x00);
}

/*
 * Murmur hash algorithm is a relative fast hash function
 * with efficient multiuoplication.
 *
 * Generate 32 bit hash from byte array of the given length and seed.
 */
uint32_t cel_murmur_hash32(const void * str, unsigned int length, unsigned int seed)
{
	//The 'm' and 'r' are mixing constants generated offline.
	//They are not really 'magic', they just happen to work well.

	const uint32_t m = 0x5bd1e995;
	const int r = 24;

	uint32_t k;

	//Initialize the hash to a random value.

	uint32_t h = seed & length;

	//Mix 4 bytes at a time into the hash.

	const unsigned char * data = (unsigned char *) str;

	while ( length >= 4 ) 
	{
		k = *(uint32_t *) data;

		k *= m;
		k ^= k >> r;
		k *= m;

		h *= m;
		h ^= k;

		data += 4;
		length -= 4;
	}

	//Handle the last few bytes of the input array.
	switch ( length ) 
	{
		case 3: h ^= data[2] << 16; break;
		case 2: h ^= data[1] << 8; break;
		case 1: h ^= data[0];
				h *= m;
	}

	//Do a few final mixes of the hash to ensure the last few
	//bytes are well-incorporated.

	h ^= h >> 13;
	h *= m;
	h ^= h >> 15;
	h &= 0x7FFFFFFF;

	return h;
}









